{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Length of Longest Fibonacci Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lenLongestFibSubseq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长的斐波那契子序列的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果序列 <code>X_1, X_2, ..., X_n</code> 满足下列条件，就说它是 <em>斐波那契式 </em>的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n >= 3</code></li>\n",
    "\t<li>对于所有 <code>i + 2 <= n</code>，都有 <code>X_i + X_{i+1} = X_{i+2}</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个<strong>严格递增</strong>的正整数数组形成序列 arr ，找到 <font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.600000381469727px\"><span style=\"caret-color:#c7254e\"><span style=\"background-color:#f9f2f4\">arr</span></span></span></font></font> 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。</p>\n",
    "\n",
    "<p><em>（回想一下，子序列是从原序列 <font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.600000381469727px\"><span style=\"caret-color:#c7254e\"><span style=\"background-color:#f9f2f4\">arr</span></span></span></font></font> 中派生出来的，它从 <font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.600000381469727px\"><span style=\"caret-color:#c7254e\"><span style=\"background-color:#f9f2f4\">arr</span></span></span></font></font> 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， <code>[3, 5, 8]</code> 是 <code>[3, 4, 5, 6, 7, 8]</code> 的一个子序列）</em></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr =<strong> </strong>[1,2,3,4,5,6,7,8]\n",
    "<strong>输出: </strong>5\n",
    "<strong>解释: </strong>最长的斐波那契式子序列为 [1,2,3,5,8] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr =<strong> </strong>[1,3,7,11,12,14,18]\n",
    "<strong>输出: </strong>3\n",
    "<strong>解释</strong>: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= arr.length <= 1000</code></li>\n",
    "\t<li>\n",
    "\t<p><code>1 <= arr[i] < arr[i + 1] <= 10^9</code></p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [length-of-longest-fibonacci-subsequence](https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [length-of-longest-fibonacci-subsequence](https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8]', '[1,3,7,11,12,14,18]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "      s = set(arr)\n",
    "      mx = 2\n",
    "      n = len(arr)\n",
    "      for i in range(n):\n",
    "        for j in range(i + 1, n):\n",
    "          a = arr[i]\n",
    "          b = arr[j]\n",
    "          tol = a + b\n",
    "          cur = 2\n",
    "          while tol in s:\n",
    "            a = b\n",
    "            b = tol\n",
    "            tol = a + b\n",
    "            cur += 1\n",
    "          mx = max(mx, cur)\n",
    "      return mx if mx >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n, idx_map, ans = len(arr), {num: i for i, num in enumerate(arr)}, 0\n",
    "        dp = defaultdict(lambda: defaultdict(lambda: 2))\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if (nxt := arr[i] + arr[j]) in idx_map:\n",
    "                    dp[j][idx_map[nxt]] = dp[i][j] + 1\n",
    "                    ans = max(ans, dp[j][idx_map[nxt]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n, idx_map, ans = len(arr), {num:i for i, num in enumerate(arr)}, 0\n",
    "        from collections import defaultdict\n",
    "        dp = defaultdict(lambda:defaultdict(lambda:2))\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if (nxt:=arr[i] + arr[j]) in idx_map:\n",
    "                    dp[j][idx_map[nxt]] = dp[i][j] + 1\n",
    "                    ans = max(ans, dp[j][idx_map[nxt]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        memo = defaultdict(int)\n",
    "        for i, a in enumerate(arr):\n",
    "            memo[a] = i\n",
    "        @functools.lru_cache() # 如果设置为None会导致MLE\n",
    "        def dfs(i, j):\n",
    "            if j == n - 1:\n",
    "                return 2 # 最小答案为2\n",
    "            ans = 2\n",
    "            k = i + j\n",
    "            if k in memo:\n",
    "                ans = max(ans, dfs(j, k) + 1)\n",
    "            return ans\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                ans = max(ans, dfs(arr[i], arr[j]))\n",
    "        return ans if ans != 2 else 0 # 为2时不满足长度要求，返回0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dic = { v : i for i, v in enumerate(arr) }\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j) :\n",
    "            if i == n :\n",
    "                return 0\n",
    "            \n",
    "            if arr[i] + arr[j] in dic:\n",
    "                return dfs(j, dic[arr[i] + arr[j]]) + 1\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in range(n) :\n",
    "            for j in range(i+1, n) :\n",
    "                if arr[i] + arr[j] in dic :\n",
    "                    ans = max(ans, dfs(j, dic[arr[i] + arr[j]]) + 3)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\r\n",
    "        cache={}\r\n",
    "        def dfs(p1,p2):\r\n",
    "            if (p1,p2) in cache:\r\n",
    "                return cache[(p1,p2)]\r\n",
    "            nxt=p1+p2\r\n",
    "            if nxt in num_pos:\r\n",
    "                l=1+dfs(p2,nxt)\r\n",
    "                cache[(p1,p2)]=l\r\n",
    "                return l\r\n",
    "            else:\r\n",
    "                return 0\r\n",
    "        ret=0\r\n",
    "        num_pos={n:i for i,n in enumerate(arr)}\r\n",
    "        n=len(arr)\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(i+1,n):\r\n",
    "                l=dfs(arr[i],arr[j])\r\n",
    "                if l>0:\r\n",
    "                    ret=max(ret,2+dfs(arr[i],arr[j]))\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr_set = set(arr)\n",
    "        arr_dict = {v:idx for idx,v in enumerate(arr)}\n",
    "        @cache\n",
    "        def dp(j,i):\n",
    "            if arr[i]-arr[j]>=arr[j] or arr[i]-arr[j] not in arr_set:\n",
    "                return 0\n",
    "            else:\n",
    "                k = arr_dict[arr[i]-arr[j]]\n",
    "                if 0<=k<j:\n",
    "                    return max(3, dp(k, j)+1)\n",
    "                else:\n",
    "                    return 0\n",
    "        res = 0\n",
    "        for i in range(1, len(arr)):\n",
    "            for j in range(i):\n",
    "                if arr[i]-arr[j]>=arr[j] or arr[i]-arr[j] not in arr_set:\n",
    "                    continue\n",
    "                res = max(dp(j, i), res)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        s=set(arr)\n",
    "        index={}\n",
    "        for i in range(len(arr)):\n",
    "            index[arr[i]]=i\n",
    "        n=len(arr)\n",
    "        dp=[]\n",
    "        for i in range(n):\n",
    "            dp.append([])\n",
    "            for j in range(i):\n",
    "                dp[-1].append(0)\n",
    "        for i in range(2,n):\n",
    "            ans=0\n",
    "            for j in range(i):\n",
    "                if arr[j]*2<=arr[i]:\n",
    "                    continue\n",
    "                if arr[i]-arr[j] in s:\n",
    "                    ind=index[arr[i]-arr[j]]\n",
    "                    if dp[j][ind]==0:\n",
    "                        dp[i][j]=3\n",
    "                    else:\n",
    "                        dp[i][j]=dp[j][ind]+1\n",
    "        return max([max(dp[i]) for i in range(1,n)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        n, res = len(A), 0\n",
    "        a = [[0] * n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            lo, hi, v = 0, i - 1, A[i]\n",
    "            while lo < hi:\n",
    "                if A[lo] + A[hi] < v:\n",
    "                    lo += 1\n",
    "                elif A[lo] + A[hi] > v:\n",
    "                    hi -= 1\n",
    "                else:\n",
    "                    if a[lo][hi]:\n",
    "                        a[hi][i] = a[lo][hi] + 1\n",
    "                    else:\n",
    "                        a[hi][i] = 3\n",
    "                    res = max(a[hi][i], res)\n",
    "                    lo += 1\n",
    "                    hi -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr_set = set(arr)\n",
    "        arr_dict = {v:idx for idx,v in enumerate(arr)}\n",
    "        # @cache\n",
    "        def dp(j,i):\n",
    "            if arr[i]-arr[j]>=arr[j] or arr[i]-arr[j] not in arr_set:\n",
    "                return 0\n",
    "            else:\n",
    "                k = arr_dict[arr[i]-arr[j]]\n",
    "                if 0<=k<j:\n",
    "                    return max(3, dp(k, j)+1)\n",
    "                else:\n",
    "                    return 0\n",
    "        res = 0\n",
    "        for i in range(1, len(arr)):\n",
    "            for j in range(i):\n",
    "                res = max(dp(j, i), res)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        d = {}\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            d[A[i]] = i\n",
    "            for j in range(i):\n",
    "                dp[j][i] = 2\n",
    "                if A[i] - A[j] in d and A[i] - A[j] < A[j]:\n",
    "                    dp[j][i] = dp[d[A[i] - A[j]]][j] + 1\n",
    "                    result = max(result, dp[j][i])\n",
    "        return result if result > 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        ans=0\n",
    "        hashmap=dict()\n",
    "        for index, v in enumerate(A):\n",
    "            hashmap[v]=index\n",
    "        dp=[[2]*len(A) for _ in range(len(A))]\n",
    "       # dp=collections.defaultdict(lambda:2)\n",
    "        for i in range(len(A)):\n",
    "            for j in range(i):\n",
    "                f=hashmap.get(A[i]-A[j],None)\n",
    "               # print(f)\n",
    "                if f is not None and f<j:\n",
    "                    dp[j][i]=max(dp[j][i],dp[f][j]+1)\n",
    "                    ans=max(ans,dp[j][i])\n",
    "        return ans if ans>=3 else 0\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        max_l = 0\n",
    "        self.num_index = {x:index for index,x in enumerate(arr)}\n",
    "        self.arr = arr\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                tmp = arr[i] + arr[j]\n",
    "                if tmp in self.num_index:\n",
    "                    max_l = max(max_l, self.dfs(i,j))\n",
    "        return max_l\n",
    "    @lru_cache(None)\n",
    "    def dfs(self,i,j):\n",
    "        tmp = self.arr[i] + self.arr[j]\n",
    "        if tmp in self.num_index:\n",
    "            i =j\n",
    "            j=self.num_index[tmp]\n",
    "            return 1+ self.dfs(i,j)\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        hash_map = {}\n",
    "        l = len(A)\n",
    "        # 最核心：结尾两个数字的选择，从前往后会超时\n",
    "        for i in range(l):\n",
    "            hash_map[A[i]] = i\n",
    "\n",
    "        # 建表格\n",
    "        max_len = 0\n",
    "        dp = [[2 for _ in range(l)] for _ in range(l)]\n",
    "        for j in range(l-1,0,-1):\n",
    "            for i in range(j - 1,-1,-1):\n",
    "                dist = A[j] - A[i]\n",
    "                if hash_map.get(dist) != None and hash_map[dist] < i:\n",
    "                    dp[hash_map[dist]][i] = dp[i][j] + 1\n",
    "                    max_len = max(max_len,dp[hash_map[dist]][i])\n",
    "        \n",
    "        return max_len if max_len > 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        ans, n = 0, len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if arr[j] * 2 <= x:\n",
    "                    break\n",
    "                if x - arr[j] in indices:\n",
    "                    k = indices[x - arr[j]]\n",
    "                    dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        def find(num,start):\n",
    "            tmp=bisect_left(arr,num,start)\n",
    "            return tmp if tmp < len(arr) and arr[tmp]==num else -1\n",
    "        cache={}\n",
    "        def dfs(i,j):\n",
    "            if (i,j) in cache:\n",
    "                return cache[(i,j)]\n",
    "            n=find(arr[i]+arr[j],j+1)\n",
    "            \n",
    "            if n!=-1:\n",
    "                ans=1+dfs(j,n)\n",
    "            else:\n",
    "                ans=2\n",
    "            if i<=100 and j <=100:\n",
    "                cache[(i,j)]=ans\n",
    "            return ans\n",
    "        ans=0\n",
    "        for i in range(len(arr)-1):\n",
    "            for j in range(i+1,len(arr)):\n",
    "                ans=max(ans,dfs(i,j))\n",
    "        return ans if ans >2 else 0   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        index = dict()\n",
    "        #for i, num in enumerate(arr):\n",
    "        #    index[num] = i\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dp[i][j] = 2\n",
    "                temp = arr[i] - arr[j]\n",
    "                if temp in index and index[temp] < j:\n",
    "                    pos = index[temp]\n",
    "                    temp2 = arr[j] - temp\n",
    "                    if temp2 in index and index[temp2] < pos:\n",
    "                        dp[i][j] += dp[pos][index[temp2]]\n",
    "                    else:\n",
    "                        dp[i][j] += 1\n",
    "                ans = max(ans, dp[i][j])\n",
    "            index[arr[i]] = i\n",
    "        return ans if ans > 2 else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        valToIndex = {}\n",
    "        for i, num in enumerate(arr):\n",
    "            valToIndex[num] = i\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if arr[i] - arr[j] >= arr[j]:\n",
    "                    break\n",
    "\n",
    "                if arr[i] - arr[j] in valToIndex:\n",
    "                    k = valToIndex[arr[i] - arr[j]]\n",
    "                    dp[i][j] = max(dp[j][k], 2) + 1\n",
    "                    res = max(res, dp[i][j])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#最长的斐波那契子序列的长度,动态规划\n",
    "\n",
    "#当 i>j 时，dp[j][i] 表示以 arr[j] 和 arr[i] 作为最后两个数字的斐波那契子序列的最大长度\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        num2idx={num:i for i,num in enumerate(arr)}\n",
    "        ans,n=0,len(arr)\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        for i,x in enumerate(arr):\n",
    "            for j in range(n-1,-1,-1):#倒序遍历\n",
    "                if arr[j]*2<=x:break #arr[i],arr[j],x\n",
    "                if x-arr[j] in num2idx:\n",
    "                    k=num2idx[x-arr[j]]\n",
    "                    dp[j][i]=max(dp[k][j]+1,3)\n",
    "                    ans=max(ans,dp[j][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        lenr = len(arr)\n",
    "        ans = 0\n",
    "        dp = [[0 for _ in range(lenr)] for _ in range(lenr)]\n",
    "        numdict = {arr[i]: i for i in range(lenr)}\n",
    "        for i in range(lenr):\n",
    "            for j in range(i+1, lenr):\n",
    "                l = arr[i]\n",
    "                r = arr[j]\n",
    "                nxt = l + r\n",
    "                res = 2\n",
    "                while nxt in numdict:\n",
    "                    l = r\n",
    "                    r = nxt\n",
    "                    nxt = l+r\n",
    "                    res += 1\n",
    "                ans = max(ans, res)\n",
    "        return 0 if ans < 3 else ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [ [ 0 for _ in range(n) ]  for _ in range(n) ]\n",
    "        idx = {x: i for i, x in enumerate(arr)}\n",
    "        ans = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if x - arr[j] < arr[j] and x - arr[j] in idx:\n",
    "                    k = idx[x-arr[j]]\n",
    "                    dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                    #print(k, j, i, dp[j][i])\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def lenLongestFibSubseq(self, A):\n",
    "        S = set(A)\n",
    "        ans = 0\n",
    "        for i in range(len(A)):\n",
    "            for j in range(i+1, len(A)):\n",
    "                \"\"\"\n",
    "                With the starting pair (A[i], A[j]),\n",
    "                y represents the future expected value in\n",
    "                the fibonacci subsequence, and x represents\n",
    "                the most current value found.\n",
    "                \"\"\"\n",
    "                x, y = A[j], A[i] + A[j]\n",
    "                length = 2\n",
    "                while y in S:\n",
    "                    x, y = y, x + y\n",
    "                    length += 1\n",
    "                ans = max(ans, length)\n",
    "        return ans if ans >= 3 else 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "\n",
    "        s=set(A)\n",
    "\n",
    "        result=0\n",
    "\n",
    "        for i in range(len(A)-1):\n",
    "            for j in range(i+1,len(A)):\n",
    "                tmp1=A[i]\n",
    "                tmp2=A[j]\n",
    "                count=2\n",
    "                while  tmp1+tmp2 in s:\n",
    "                    tmp1,tmp2=tmp2,tmp1+tmp2\n",
    "                    count=count+1\n",
    "                    result=max(result,count)\n",
    "        return result if result>0 else 0\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, a: [int]) -> int:\n",
    "        n = len(a)\n",
    "        preidx = [[-1]*n for i in range(n)]\n",
    "\n",
    "        def find(l, r, t):\n",
    "            if l > r:\n",
    "                return -1\n",
    "            if a[l] > t:\n",
    "                return -1\n",
    "            if a[r] < t:\n",
    "                return -1\n",
    "            if t == a[l]:\n",
    "                return l\n",
    "            if t == a[r]:\n",
    "                return r\n",
    "            while l <= r:\n",
    "                m = (l+r)//2\n",
    "                if a[m] == t:\n",
    "                    return m\n",
    "                if a[m] < t:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            return -1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                pre = a[j] - a[i]\n",
    "                pi = find(0, i-1, pre)\n",
    "                preidx[i][j] = pi\n",
    "        # for c in preidx:\n",
    "        #     print(c)\n",
    "        f = [[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                pi = preidx[i][j]\n",
    "                if pi >= 0:\n",
    "                    f[i][j] = 1 + f[pi][i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, max(f[i]))\n",
    "        if ans > 0:\n",
    "            return ans+2\n",
    "        return 0\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print(Solution().lenLongestFibSubseq([1, 2, 3, 4, 5, 6, 7, 8]))\n",
    "    print(Solution().lenLongestFibSubseq([1, 3, 7, 11, 12, 14, 18]))\n",
    "    print(Solution().lenLongestFibSubseq([1, 3, 5]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[[0 for _ in range (n)] for _ in range(n)]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                dp[i][j]=2\n",
    "\n",
    "\n",
    "        n=len(arr)\n",
    "        maxlen=0\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        for k in range(2,n):\n",
    "            i=0\n",
    "            j=k-1\n",
    "            while i<j:\n",
    "                if arr[i]+arr[j]==arr[k]:\n",
    "                    dp[j][k]=dp[i][j]+1\n",
    "                    maxlen=max(maxlen,dp[j][k])\n",
    "                    i+=1\n",
    "                    j-=1\n",
    "                if arr[i]+arr[j]<arr[k]:\n",
    "                    i+=1\n",
    "                if arr[i]+arr[j]>arr[k]:\n",
    "                    j-=1\n",
    "        return 0 if maxlen==0 else maxlen+2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        if(len(A) <= 2):\n",
    "            return 0\n",
    "        else:\n",
    "            res = 2\n",
    "            dic = [{} for _ in range(len(A))]\n",
    "            for i in range(len(A)):\n",
    "                for j in range(i):\n",
    "                    num = A[i] - A[j]\n",
    "                    if(num in dic[j]):\n",
    "                        dic[i][A[j]] = dic[j][num] + 1\n",
    "                    else:\n",
    "                        dic[i][A[j]] = 2\n",
    "                    res = max(res, dic[i][A[j]])\n",
    "            return res if res >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        f = [{} for x in range(n)]\n",
    "        # 赋予初值\n",
    "        res = 2\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                f[j][A[i]] = 2\n",
    "        \n",
    "        for i in range(2,n):\n",
    "            for j in range(i):\n",
    "                last = A[i]-A[j]\n",
    "                if(last in f[j]):\n",
    "                    f[i][A[j]] = f[j][last] + 1\n",
    "                    res = max(res,f[i][A[j]])\n",
    "        if(res>=3):\n",
    "            return res\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int: \n",
    "        n = len(arr)\n",
    "        dp = [[0 for i in range(n)] for j in range(n)]\n",
    "        index = {x:i for i, x in enumerate(arr)}\n",
    "        ans, n = 0, len(arr)\n",
    "        dp = [[0 for i in range(n)] for j in range(n)]\n",
    "        for i, x in enumerate(arr):\n",
    "            if i<2:\n",
    "                continue\n",
    "            end = arr[i]\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if arr[j]*2<end:\n",
    "                    break\n",
    "                if end-arr[j] in index:\n",
    "                    k = index[end-arr[j]]\n",
    "                    if k>=0 and k<j:\n",
    "    #                     当dp[k][j]等于0时，说明k,j不能单独构成斐波那契数列，因此最终的结果为最小斐波那契数列长度，也就是3.\n",
    "                        dp[j][i] = max(dp[k][j]+1, 3)\n",
    "                        ans = max(ans, dp[j][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        idx_map = {num: i for i, num in enumerate(arr)}\n",
    "        ans = 0\n",
    "        dp = defaultdict(lambda: 2)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if (nxt := arr[i] + arr[j]) in idx_map:\n",
    "                    dp[j,idx_map[nxt]] = dp[i,j] + 1\n",
    "                    # ans = max(ans, dp[j,idx_map[nxt]])\n",
    "        max_value = 0\n",
    "        for key in dp:\n",
    "            if dp[key] > max_value:\n",
    "                max_value = dp[key]\n",
    "        return 0 if max_value == 2 else max_value\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        f = [{} for i in range(len(arr))]\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i):\n",
    "                f[i][arr[j]] = f[j].get(arr[i]-arr[j], 1) + 1\n",
    "                ans = max(ans, f[i][arr[j]])\n",
    "\n",
    "        if ans<3:\n",
    "            return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        dp = defaultdict(dict)\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i):\n",
    "                d = arr[i] - arr[j]\n",
    "                if d in dp[arr[j]]:\n",
    "                    dp[arr[i]][arr[j]] = dp[arr[j]][d] + 1\n",
    "                else:\n",
    "                    dp[arr[i]][arr[j]] = 2\n",
    "                res = max(res, dp[arr[i]][arr[j]])\n",
    "        if res < 3:\n",
    "            return 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        dp = [{0:0} for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dp[i][a[j]] = dp[j].get(a[i]-a[j],1)+1\n",
    "        res = max(max(x.values()) for x in dp)\n",
    "        return res if res >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = []\n",
    "        for l in range(n):\n",
    "            ans = {}\n",
    "            if l == 0:\n",
    "                dp.append({\" \" : 1})\n",
    "            else:\n",
    "                 for i in range(0, l):\n",
    "                    pre = arr[l] - arr[i]\n",
    "                    if pre in dp[i]:\n",
    "                        ans[arr[i]] = dp[i].get(pre) + 1\n",
    "                    else:\n",
    "                        ans[arr[i]] = 2\n",
    "                 dp.append(ans)\n",
    "        res = max(max(dp[j].values()) for j in range(len(arr)))\n",
    "        if res != 2:\n",
    "            return res\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        preDiff = collections.defaultdict(dict)\n",
    "\n",
    "        n = len(arr)\n",
    "        maxLen = 0\n",
    "        for j in range(1, n):\n",
    "            for i in range(j):\n",
    "                if arr[j] - arr[i] in preDiff[arr[i]]:\n",
    "                    preDiff[arr[j]][arr[i]] = preDiff[arr[i]][arr[j]-arr[i]] + 1\n",
    "                    maxLen = max(maxLen, preDiff[arr[j]][arr[i]])\n",
    "                else:\n",
    "                    preDiff[arr[j]][arr[i]] = 2\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        indices={x:i for i,x in enumerate(arr)}\n",
    "        dp=np.zeros((n,n),dtype=np.int32)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                # 不能递增，肯定不能满足前面的是fib\n",
    "                if arr[j]*2<=arr[i]:\n",
    "                    break\n",
    "                if arr[i]-arr[j] in indices:\n",
    "                    k=indices[arr[i]-arr[j]]\n",
    "                    dp[i,j]=max(3,dp[j,k]+1)\n",
    "                    ans=max(ans,dp[i,j])\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        r = 0\n",
    "        arr_set = set(arr)\n",
    "        cache = {}\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                now_len = 1\n",
    "                x0 = arr[i]\n",
    "                x1 = arr[j]\n",
    "                if x1 in cache.get(x0, set({})):\n",
    "                    continue\n",
    "                while x1 in arr_set:\n",
    "                    if x0 not in cache:\n",
    "                        cache[x0] = set({})\n",
    "                    cache[x0].add(x1)\n",
    "                    tmp = x0 + x1\n",
    "                    x0 = x1\n",
    "                    x1 = tmp\n",
    "                    \n",
    "                    now_len += 1\n",
    "                if now_len > 2:\n",
    "                    r = max(r, now_len)\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Dict, List, Set\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        length = len(arr)\n",
    "        set0 = set(arr)\n",
    "        cache:Dict[int, Set[int]] = defaultdict(set)\n",
    "        maxLength = 2\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length):\n",
    "                a, b = arr[i], arr[j]\n",
    "                ans = 2\n",
    "                while True:\n",
    "                    if b in cache[a]:\n",
    "                        break\n",
    "                    cache[a].add(b)\n",
    "                    c = a + b\n",
    "                    if c in set0:\n",
    "                        a, b = b, c\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "                maxLength = max(maxLength, ans)\n",
    "        return maxLength if maxLength > 2 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        table = {}\n",
    "        for i, n in enumerate(arr):\n",
    "            table[n] = i\n",
    "        \n",
    "        # 记L[i, j]表示以arr[i]为倒数第一个数, arr[j]为倒数第二个数的斐波那契子序列长度\n",
    "        import numpy as np\n",
    "        L = np.zeros([len(arr), len(arr)], dtype=int)\n",
    "        # L[i, j] = L[j, i - j] + 1 if i - j in table and j > i - j else 2\n",
    "        for j in range(len(arr)):\n",
    "            for i in range(j + 1, len(arr)):\n",
    "                delta = arr[i] - arr[j]\n",
    "                if delta in table and j > table[delta]:\n",
    "                    L[i, j] = L[j, table[delta]] + 1\n",
    "                else:\n",
    "                    L[i, j] = 2\n",
    "        m = int(np.max(L))\n",
    "        return m if m >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        res = 2\n",
    "        index_map = {val: i for i, val in enumerate(arr)}\n",
    "        dp = np.zeros(shape=(n, n))\n",
    "        dp[0, 1] = 2\n",
    "        for i in range(2, n):\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "                dp[j, i] = 2\n",
    "                if (arr[i] - arr[j]) in index_map.keys():\n",
    "                    index = index_map.get(arr[i] - arr[j])\n",
    "                    if j <= index:\n",
    "                        j -= 1\n",
    "                        continue\n",
    "                    dp[j, i] = dp[index, j] + 1\n",
    "                    res = max(res, dp[j, i])\n",
    "                j -= 1\n",
    "        return int(res) if res != 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        res = 2\n",
    "        index_map = {val: i for i, val in enumerate(arr)}\n",
    "        dp = np.zeros(shape=(n, n))\n",
    "        dp[0, 1] = 2\n",
    "        for i in range(2, n):\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "                dp[j, i] = 2\n",
    "                if (arr[i] - arr[j]) in index_map.keys():\n",
    "                    index = index_map.get(arr[i] - arr[j])\n",
    "                    if j < index:\n",
    "                        j -= 1\n",
    "                        continue\n",
    "                    dp[j, i] = dp[index, j] + 1\n",
    "                    res = max(res, dp[j, i])\n",
    "                j -= 1\n",
    "        return int(res) if res != 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, ilist: List[int]) -> int:\n",
    "        longest=dict.fromkeys([i for i in range(len(ilist))],{})\n",
    "        longest={}\n",
    "        l_set=set(ilist)\n",
    "        for i in range(len(ilist)): #i 代表第二个数\n",
    "            longest[i]={}\n",
    "            for j in range(i): #j代表第一个数\n",
    "                longest[i][j]=2\n",
    "        for i,k in enumerate(ilist):\n",
    "            try:\n",
    "                for j in longest[i].keys():\n",
    "                    z=ilist[i]+ilist[j]\n",
    "                    if z in l_set: \n",
    "                        i_z=ilist.index(z)\n",
    "                        longest[i_z][i]=longest[i][j]+1\n",
    "            except:\n",
    "                print(\"i:{}   i_z:{}\".format(i,i_z))\n",
    "        max_l=0\n",
    "        for i in longest.keys():\n",
    "            for j in longest[i].keys():\n",
    "                if longest[i][j]>max_l:\n",
    "                    max_l=longest[i][j]\n",
    "        return max_l if max_l>2 else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        \n",
    "        _dict = dict()\n",
    "        n = len(A)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(2):\n",
    "            _dict[A[i]] = i\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            _dict[A[i]] = i\n",
    "                \n",
    "            for j in range(i-1, -1, -1):\n",
    "                \n",
    "                cur = A[i] - A[j]\n",
    "                if cur >= A[j]:\n",
    "                    break\n",
    "                \n",
    "                if cur in _dict:\n",
    "                    dp[i][j] = max(dp[_dict[A[j]]][_dict[cur]]+1, dp[i][j])\n",
    "                \n",
    "        import numpy as np\n",
    "        #print(np.array(dp))\n",
    "        #print(_dict)\n",
    "        _max = np.max(dp)\n",
    "        if _max == 0:\n",
    "            return 0\n",
    "        return _max + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        _dict = dict()\n",
    "        n = len(A)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(2):\n",
    "            _dict[A[i]] = i\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            _dict[A[i]] = i\n",
    "                \n",
    "            for j in range(i-1, -1, -1):\n",
    "                \n",
    "                cur = A[i] - A[j]\n",
    "                if cur >= A[j]:\n",
    "                    break\n",
    "                \n",
    "                if cur in _dict:\n",
    "                    dp[i][j] = max(dp[_dict[A[j]]][_dict[cur]]+1, dp[i][j])\n",
    "                \n",
    "        import numpy as np\n",
    "        #print(np.array(dp))\n",
    "        #print(_dict)\n",
    "        _max = np.max(dp)\n",
    "        if _max == 0:\n",
    "            return 0\n",
    "        return _max + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        def dic():\n",
    "            return defaultdict(int)\n",
    "        pi = dict()\n",
    "        for idx, x in enumerate(arr):\n",
    "            pi[x] = idx\n",
    "        dp = defaultdict(dic)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                diff = arr[i] - arr[j]\n",
    "                # pi[diff]\n",
    "                if diff in pi:\n",
    "                    dp[i][j] = dp[j][pi[diff]] + 1\n",
    "                dp[i][j] = max(2, dp[i][j])\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans if ans > 2 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        dp = [collections.defaultdict(int) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            j = i-1\n",
    "            temp = 0\n",
    "            while j >= 0 and A[i] - A[j] < A[j]:\n",
    "                a = dp[j][A[i] - A[j]] + 2\n",
    "                temp = max(temp, a)\n",
    "                dp[i][A[j]] = a - 1\n",
    "                j -= 1\n",
    "            while j >= 0:\n",
    "                dp[i][A[j]] = 1\n",
    "                j -= 1\n",
    "            ans = max(ans, temp)\n",
    "        return ans if ans > 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        dp=[[0 for n in range(m+1)]for m in range(len(arr))]\n",
    "        re=collections.defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(len(arr)):\n",
    "            re[arr[i]]=i+1\n",
    "            dp[i][i]=1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if arr[i]-arr[j]>=arr[j]:\n",
    "                    break\n",
    "                if re[arr[i]-arr[j]] == 0:\n",
    "                    continue\n",
    "                dp[i][j]=1+dp[j][re[arr[i]-arr[j]]-1]\n",
    "                ans=max(ans,dp[i][j])\n",
    "        return ans+2 if ans!=0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        ans=[{} for i in range(len(A))]\n",
    "        max_len=0\n",
    "        for i in range(1,len(A)):\n",
    "            for j in range(i):\n",
    "                if A[i] in ans[j]:\n",
    "                    ans[i][A[i]+A[j]]=ans[j][A[i]]+1\n",
    "                else:\n",
    "                    ans[i][A[i]+A[j]]=2\n",
    "                if ans[i][A[i]+A[j]]>max_len:\n",
    "                    max_len=ans[i][A[i]+A[j]]\n",
    "        return max_len if max_len>2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        dp = [{} for _ in range(len(A))]\n",
    "        dp[1][A[0]+A[1]] = 2\n",
    "        res = 2\n",
    "        for i in range(2, len(A)):\n",
    "            for j in range(i):\n",
    "                s = A[j] + A[i]\n",
    "                if A[i] in dp[j]:\n",
    "                    dp[i][s] = dp[j][A[i]] + 1\n",
    "                    res = max(res, dp[i][s])\n",
    "                else:\n",
    "                    dp[i][s] = 2\n",
    "        return res if res != 2 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: list[int]) -> int:\n",
    "        def is_in(v, lo, hi):\n",
    "            import bisect\n",
    "            index = bisect.bisect_left(arr, v, lo, hi)\n",
    "            return index < hi and arr[index] == v\n",
    "\n",
    "        visited = set()\n",
    "        result = 0\n",
    "        k = (5 ** 0.5 - 1) / 2\n",
    "        b_limit = arr[-2] + (1 + k) * arr[-1]\n",
    "        for i in range(len(arr) - 2):\n",
    "            for j in range(i + 1, len(arr) - 1):\n",
    "                a0, a1 = arr[i], arr[j]\n",
    "                if (a0, a1) in visited:\n",
    "                    continue\n",
    "                b0 = a0 + (1 + k) * a1\n",
    "                bn = (1 + k) ** result * b0\n",
    "                if bn > b_limit:\n",
    "                    break\n",
    "                count = 0\n",
    "                visited.add((a0, a1))\n",
    "                while is_in(a2 := a0 + a1, j + 1, len(arr)):\n",
    "                    visited.add((a1, a2))\n",
    "                    count += 1\n",
    "                    a0, a1 = a1, a2\n",
    "                result = max(result, count)\n",
    "\n",
    "        return result and result + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        r = [dict((arr[j],j) for j in range(i+1,n)) for i in range(n)]\n",
    "        ma = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                s,f = i,j\n",
    "                l = 2\n",
    "                while f<n:\n",
    "                    _temp = arr[s]+arr[f]\n",
    "                    if  _temp in r[f]:\n",
    "                        s,f = f,r[s][arr[s]+arr[f]]\n",
    "                        l+=1\n",
    "                        ma = max(l,ma)\n",
    "                        #print(r[s],s,_temp,ma)\n",
    "                        del r[s][_temp]\n",
    "                    else:\n",
    "                        break\n",
    "        return ma\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        dict={}\n",
    "        dict1={}\n",
    "        num=0\n",
    "        if len(arr)==3:\n",
    "            if arr[0]+arr[1]==arr[2]:\n",
    "                num=3\n",
    "        if len(arr)>3:\n",
    "            dict1[arr[0]]=0\n",
    "            dict[0]=dict1\n",
    "            dict1={}\n",
    "            dict1[arr[0]+arr[1]]=2\n",
    "            dict[1]=dict1\n",
    "            dict1={}\n",
    "            if arr[0]+arr[1]==arr[2]:\n",
    "                num=3\n",
    "                dict1[arr[0]+arr[2]]=2\n",
    "                dict1[arr[2]+arr[1]]=3\n",
    "            else:\n",
    "                dict1[arr[0]+arr[2]]=2\n",
    "                dict1[arr[2]+arr[1]]=2\n",
    "            dict[2]=dict1\n",
    "            dict1={}\n",
    "            for i in range(3,len(arr)):\n",
    "                if i!=len(arr)-1:\n",
    "                    dict1[arr[i]+arr[0]]=2   \n",
    "                for j in range(1,i):\n",
    "                    if arr[i] in dict[j]:\n",
    "                        if dict[j][arr[i]]!=0:\n",
    "                            dict1[arr[i]+arr[j]]=dict[j][arr[i]]+1\n",
    "                    else:\n",
    "                        dict1[arr[i]+arr[j]]=2   \n",
    "                    num=max(num,dict1[arr[i]+arr[j]])\n",
    "                dict[i]=dict1\n",
    "                dict1={}\n",
    "        if num>2:\n",
    "            return num\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, nums: List[int]) -> int:\n",
    "        # 效仿 1027. 最长等差数列 https://leetcode.cn/problems/longest-arithmetic-subsequence/\n",
    "        n = len(nums)\n",
    "        f = [{} for _ in range(n)] \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                # (nums[i], nums[i] - nums[j]) , (nums[j], nums[j] - (nums[i] - nums[j]))\n",
    "                d = nums[i] - nums[j]  # 与前一个选择的元素的差\n",
    "                d2 = nums[j] - (nums[i] - nums[j])\n",
    "                f[i][d] = max(f[i].get(d, 1), f[j].get(d2, 1) + 1) # get不到值默认为1,相当于nums[i]/nums[j]是 LAS 的首项\n",
    "                res = max(res, f[i][d])\n",
    "\n",
    "        return res if res >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # #DP, dp[j][k] denotes the size of Fibonacci  subsequence with last numbers are arr[j] and arr[k]\n",
    "    # def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "    #     map_num = {val:idx for idx,val in enumerate(arr)}\n",
    "    #     n = len(arr)\n",
    "    #     dp = {j:{k:2 for k in range(j, n)} for j in range(n-1)}\n",
    "    #     res = 0\n",
    "    #     #transfer formula: dp[j][k] = dp[i][j] + 1 (if arr[i]+arr[j]==arr[k])\n",
    "    #     for j in range(1,n-1):\n",
    "    #         for k in range(j+1, n):\n",
    "    #             if arr[k]-arr[j] in map_num and map_num[arr[k]-arr[j]] < j:\n",
    "    #                 dp[j][k] = dp[map_num[arr[k]-arr[j]]][j] + 1\n",
    "    #                 res = max(res, dp[j][k])\n",
    "    #     return res\n",
    "\n",
    "\n",
    "    #optimized DP, dp[j][k] denotes the size of Fibonacci  subsequence with last numbers are arr[j] and arr[k]\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        # map_num = {val:idx for idx,val in enumerate(arr)}\n",
    "        map_num ={}\n",
    "        n = len(arr)\n",
    "        dp = {j:{k:2 for k in range(j, n)} for j in range(n-1)}\n",
    "        res = 0\n",
    "        #transfer formula: dp[j][k] = dp[i][j] + 1 (if arr[i]+arr[j]==arr[k])\n",
    "        for j in range(n-1):\n",
    "            for k in range(j+1, n):\n",
    "                if arr[k]-arr[j] in map_num:\n",
    "                    dp[j][k] = dp[map_num[arr[k]-arr[j]]][j] + 1\n",
    "                    res = max(res, dp[j][k])\n",
    "            map_num[arr[j]] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[{} for i in range(n)]\n",
    "        ans=0\n",
    "        for i,x in enumerate(arr):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                t=x-arr[j]\n",
    "                if t not in dp[i]:\n",
    "                    z=arr[j]-t\n",
    "                    dp[i][t]=dp[j].get(z,1)+1\n",
    "                    ans=max(ans,dp[i][t])\n",
    "        \n",
    "        return ans if ans!=2 else 0\n",
    "                \n",
    "                    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
